#include "UnionFind.h"

UnionFind::UnionFind(unsigned  int cantNodos){
	//Cada nodo pertenece a un grupo diferente, el grupo se representa por la raíz del arbol que contiene
	idGrupo = new unsigned int[cantNodos+1];
	sizeGrupo = new unsigned int[cantNodos+1];
	for (unsigned int i = 1; i <= cantNodos; ++i){
		idGrupo[i] = i;
		sizeGrupo[i] = 1;
	}
}

UnionFind::~UnionFind(){
	delete(idGrupo);
	delete(sizeGrupo);
}

bool UnionFind::find(unsigned int nodoU,unsigned int nodoV){
	//Si los grupos a los que pertenecen los nodos tienen la misma raiz, entonces pertenecen al mismo grupo.
	return raiz(nodoU) == raiz(nodoV);		
}

//Obtengo el representante del grupo(raíz del arbol)
unsigned int UnionFind::raiz(unsigned int nodo){
	while(nodo != idGrupo[nodo]){
		idGrupo[nodo] = idGrupo[idGrupo[nodo]];	//path Compression
		nodo = idGrupo[nodo];
	}
	return nodo;
}

void UnionFind::unioN(unsigned int nodoU,unsigned int nodoV){
	//Obtengo los representantes de los grupos a los que pertenecen los nodos.
	unsigned int i = raiz(nodoU);
	unsigned int j = raiz(nodoV);

	//El grupo que posee mas nodos conserva su representante, el que no, adopta el representante del otro.
	if(sizeGrupo[i] < sizeGrupo[j])
	{
		idGrupo[i] = j;
		sizeGrupo[j] += sizeGrupo[i];
	}
	else
	{
		idGrupo[j] = i;
		sizeGrupo[i] += sizeGrupo[j];
	}	
}
